package codingforgreat.lchot150;

public class Lc208 {
    public class Node{
        public boolean isend;
        public Node[] nexts;
        public Node(){
            isend = false;
            nexts = new Node[26];
        }
    }
    public Node root;
    public Lc208() {
        root = new Node();
    }

    public void insert(String word) {
        char[] ch = word.toCharArray();
        Node node = root;
        for(int i = 0;i < ch.length;i++){
            int next = ch[i] - 'a';
            if(node.nexts[next] == null){
                node.nexts[next] = new Node();
            }
            node =  node.nexts[next];
        }
        node.isend = true;
    }

    public boolean search(String word) {
        char[] ch = word.toCharArray();
        Node node = root;
        for(int i = 0;i < ch.length;i++){
            int next = ch[i] - 'a';
            if(node.nexts[next] == null){
                return false;
            }
            node = node.nexts[next];
        }
        return node.isend;
    }

    public boolean startsWith(String prefix) {
        char[] ch = prefix.toCharArray();
        Node node = root;
        for(int i = 0;i < ch.length;i++){
            int next = ch[i] - 'a';
            if(node.nexts[next] == null){
                return false;
            }
            node = node.nexts[next];
        }
        return true;

    }
}
